package org.geektimes.util;

import java.util.Random;

public class SkipList<T extends Comparable<? super T>> {

    private SkipListNode<T> head,tail;
    private int nodes;//节点总数
    private int listLevel;//层数
    private Random random;//用于投掷硬币
    private static final double PROBABILITY = 0.5;//向上提升一个层级的概率
    public SkipList(){
        random = new Random();
        clear();
    }

    public void clear(){
        head = new SkipListNode<T>(SkipListNode.HEAD_KEY,null);
        tail = new SkipListNode<T>(SkipListNode.TAIL_KEY,null);
        horizontalLink(head,tail);
        listLevel = 0;
        nodes = 0;
    }

    /**
     * 向SkipList插入数据
     * @param k
     * @param v
     */
    public void put(int k,T v){
        SkipListNode p = findNode(k);
        if(k == p.getKey()){
            p.value = v;
            return;
        }
        SkipListNode q = new SkipListNode(k,v);
        backLink(p,q);
        int currentLevel = 0;//当前所在的层级是0
        //抛硬币，加层级
        while(random.nextDouble()<PROBABILITY){
            //如果超出了高度，需要重新建一个顶层
            if(currentLevel>=listLevel){
                listLevel++;
                SkipListNode p1 = new SkipListNode(SkipListNode.HEAD_KEY,null);
                SkipListNode p2 = new SkipListNode(SkipListNode.TAIL_KEY,null);
                horizontalLink(p1,p2);
                verticalLink(p1,head);
                verticalLink(p2,tail);
                head = p1;
                tail = p2;
            }
            while (p.up == null){
                p = p.left;
            }
            p = p.up;
            SkipListNode e = new SkipListNode(k,null);
            backLink(p,e);
            verticalLink(e,q);
            q = e;
            currentLevel++;
        }
        nodes++;//节点数增加
    }

    /**
     * 在最下面一层，找到要插入的那个位置的前一个node，然后再添加数据
     * @param key
     * @return
     */
    public SkipListNode locateForInsert(int key){
        SkipListNode p = head;
        while (p.right.key != SkipListNode.TAIL_KEY && p.right.key<=key){
            p = p.right;
        }
        return p;
    }

    private SkipListNode findNode(int key){
        SkipListNode p = head;
        while (true){
            while (p.right.key != SkipListNode.TAIL_KEY && p.right.key <= key){
                p = p.right;
            }
            if(p.down != null){
                p = p.down;
            }else{
                break;
            }
        }
        return p;
    }

    /**
     * 在node1后面插入node2
     * head -> node1->node2->tail
     */
    private void backLink(SkipListNode node1,SkipListNode node2){
        node2.left = node1;
        node2.right = node1.right;
        node1.right.left = node2;
        node1.right = node2;
    }
    /**
     * 水平双向链接
     */
    private void horizontalLink(SkipListNode node1,SkipListNode node2){
        node1.right = node2;
        node2.left = node1;
    }

    /**
     * 垂直双向链接
     */
    private void verticalLink(SkipListNode node1,SkipListNode node2){
        node1.down = node2;
        node2.up = node1;
    }

    public boolean isEmpty(){
        return nodes == 0;
    }
    public int size(){
        return nodes;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "跳跃表为空！";
        }
        StringBuilder builder=new StringBuilder();
        SkipListNode<T> p=head;
        while (p.down!=null) {
            p=p.down;
        }

        while (p.left!=null) {
            p=p.left;
        }
        if (p.right!=null) {
            p=p.right;
        }
        while (p.right!=null) {
            builder.append(p);
            builder.append("\n");
            p=p.right;
        }

        return builder.toString();
    }

    public static void main(String[] args) {
        SkipList<String> list=new SkipList<String>();
        System.out.println(list);
        list.put(2, "王");
        list.put(1, "着");
        list.put(3, "榕");
        list.put(1, "要");//测试同一个key值
        list.put(4, "路");
        list.put(6, "啊");
        list.put(5, "了");
        System.out.println(list);
        System.out.println(list.size());
    }

}

class SkipListNode<T>{
    public int key;
    public T value;
    public SkipListNode<T> up,down,left,right;//上下左右 四个指针

    public static final int HEAD_KEY = Integer.MIN_VALUE;
    public static final int TAIL_KEY = Integer.MAX_VALUE;

    public SkipListNode(int key, T value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }
    public void setKey(int key) {
        this.key = key;
    }
    public T getValue() {
        return value;
    }
    public void setValue(T value) {
        this.value = value;
    }
    public boolean equals(Object o) {
        if (this==o) {
            return true;
        }
        if (o==null) {
            return false;
        }
        if (!(o instanceof SkipListNode<?>)) {
            return false;
        }
        SkipListNode<T> ent;
        try {
            ent = (SkipListNode<T>)  o; // 检测类型
        } catch (ClassCastException ex) {
            return false;
        }
        return (ent.getKey() == key) && (ent.getValue() == value);
    }
    @Override
    public String toString() {
        return "key-value:"+key+"-"+value;
    }
}
